module Dijkstra;
import tango.io.Stdout;
import tango.util.container.LinkedList;
import tango.util.container.SortedMap;
import tango.text.Ascii;
import tango.math.Math;

import tango.util.container.HashMap;

/*
class Dijkstra_Object
{
	LinkedList!(Dijkstra_Object) neighbours;
	//HashMap!(Dijkstra_Object,float) neighbour_dist;
	float [2] position;
	char[] name;
	Dijkstra_Object previous=null;
	
	this(char[] iName,float [2] pos)
	{
		position[]=pos;
		name=iName;
		neighbours=new LinkedList!(Dijkstra_Object)();
		//neighbour_dist =new HashMap!(Dijkstra_Object,float)();
	}
	
	//LinkedList!(Dijkstra_Object) getNeighbours() {return neighbours;}
	//float [] position {return position;}
	//char[] getName() {return name;}
	Dijkstra_Object getPathPrevious() {return previous;}
	void setPathPrevious(Dijkstra_Object A) {previous=A;}
	
	void attach(Dijkstra_Object B, float dist)
	{
		if (!B) return;
		
		if (!neighbours.contains(B))
		{
			neighbours.add(B);
			if (dist<0)
			{
				dist=distanceTo(B.position);
				B.attach(this,dist);
			
			}
			//neighbour_dist[B]=dist;
			
		}
		
	}
	void detach(Dijkstra_Object B)
	{
		if (neighbours.contains(B))
		{
			//neighbour_dist.removeKey(B);
			neighbours.remove(B);
			B.detach(this);
		}
		
	}
	void printNeighbours()
	{
		Stdout.format("{} neighbours :",name);
		foreach(n;neighbours)
			Stdout.format(" {}",n.name);
		Stdout.formatln("");
	}
	float distanceTo(float[] pos)
	{
		float dx=pos[0]-position[0];
		float dy=pos[1]-position[1];
		return sqrt(dx*dx+dy*dy);
	}
}

int main()
{
	auto G=new LinkedList!(Dijkstra_Object)();
	auto A=new Dijkstra_Object("A",[0f,0f]);
	auto B=new Dijkstra_Object("B",[1f,1f]);
	auto C=new Dijkstra_Object("C",[0.5f,0f]);
	auto D=new Dijkstra_Object("D",[2f,0f]);
	G.add(A);
	G.add(B);
	G.add(C);
	G.add(D);
	
	A.attach(D,-1);
	C.attach(B,-1);
	D.attach(C,-1);
	A.attach(C,-1);
	//foreach(p;G) p.printNeighbours();
	auto DK=new Dijkstra!(Dijkstra_Object)(G);
	Dijkstra_Object[] path=DK.solve(A,B);
	
	foreach(p;path) Stdout.formatln("Point {}",p.name);
	return 0;
}
*/
class DPair(T)
{
	float weight;
	T O;
	this(T A,float w)
	{
		O=A;
		weight=w;
	}

	int opEquals(Object B)
	{
		return cast(int)(weight-(cast(DPair)B).weight);
	}
	public int opCmp(Object second)
	{
		auto B= (cast(DPair)second);
		int dif=cast(int)(weight-B.weight);
		if (dif==0)
		{ 
			return compare(this.O.name,B.O.name);
		}
		return dif;
	}
}

class Dijkstra(T)
{
	LinkedList!(T) G;
	SortedMap!(DPair!(T),T) weights;
	HashMap!(T,DPair!(T)) keyIndex;
	
	this(LinkedList!(T) iG)
	{
		setPoints(iG);
	}
	
	void setPoints(LinkedList!(T) iG)
	{
		G=iG;
	}
	LinkedList!(T) solve(T START,T END)
	{
		
		weights=new SortedMap!(DPair!(T),T)();
		keyIndex=new HashMap!(T,DPair!(T))();
		DPair!(T) dp,dp2;
		T s1;
		//Stdout.formatln("Size of G : {}",G.size());
		float i=float.max;
		foreach (o;G)
		{
			dp=new DPair!(T)(o,i--);
			
			bool isnew=weights.containsKey(dp);
			weights.add(dp,o);
			//Stdout.formatln("New entry ? : {}",isnew);
		
			keyIndex[o]=dp;
			
		}
		//Stdout.formatln("Size of weights : {}",weights.size());
		//Stdout.formatln("Size of keyIndex : {}",keyIndex.size());
				
		//float w=getWeight(START); 
		setWeight(START,0f);
		//		Stdout.formatln(" A<B ? {}",(START<END));
		 
		//weights.keyOf(START,dp);
		//Stdout.formatln(" Weight of STart {}",dp.weight);
		auto Q=new LinkedList!(T)();
		while (!weights.isEmpty())
		{
				weights.take(s1);
				foreach(s2;s1.neighbours)
					updateWeights(s1,s2);
			
		}
		s1=END;
		Q.clear();				
		while (s1!=START)
		{
			
			Q.add(s1);
			s1=s1.getPathPrevious();
			if (s1 is null)
			{
				Stdout.formatln("NO PATH");
				return null;
			}
		}
		Q.add(START);
		return Q;
	}	
	float getWeight(T A)
	{
		return keyIndex[A].weight;
	}
	void setWeight(	T A,float v)
	{
		DPair!(T) key=keyIndex[A];
		//bool isin=weights.containsKey(key);
		bool isin=weights.removeKey(key);
		key.weight=v;
		//Stdout.formatln("... set {} to {}",A.getName(),v);
		
		if (isin) weights.add(key,A);
		keyIndex[A]=key;
		//Stdout.formatln("New First Key {}",weights.firstKey().O.getName());
	}
	
	 
	void updateWeights(T A,T B)
	{
		float wa=getWeight(A);
		float wb=getWeight(B);
		float nd=wa+A.distanceTo(B.position);
		if (wb>nd)
		{
			setWeight(B,nd);
			B.setPathPrevious(A);
		}
	}

}


	
